package com.lun.easy;

import com.lun.util.BinaryTree.TreeNode;

public class DiameterOfBinaryTree {
	
    public int diameterOfBinaryTree(TreeNode root) {
    	int[] max = {0};
    	diameterOfBinaryTree(root, max);
    	return max[0];
    }
    
    private int diameterOfBinaryTree(TreeNode node, int[] max) {
    	if(node == null) return 0;
    	
    	int left = 0, right = 0;
    	if(node.left != null) 
    		left = diameterOfBinaryTree(node.left, max) + 1;
    	
    	if(node.right != null)
    		right = diameterOfBinaryTree(node.right, max) + 1;
    	
    	max[0] = Math.max(max[0], left + right);
    	return Math.max(left, right);
    }
    
    
}
